package com.salim.leetcode.$142;

import java.util.List;

public class LinkedListCycleII {
    //这道题有更快的算法 在第一次相遇的点和链表起点同时开始走一步 再次相遇的点就是起始点
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode slow = head;
        ListNode fast = head;
        int count = 0;
        while (slow.next!=null&&fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(dummy.next==slow){
                return dummy.next;
            }
            //奇数圈slow走完会碰到2次 偶数圈slow走完会碰到1次
            if(slow==fast){
                if(count==1){
                    dummy = dummy.next;
                    count = 0;
                }else{
                    count++;
                }
            }
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
